package baseclass.k_array;

import java.util.*;

/**
 * 有一数组arr长度len，设滑动窗口为1 <= K  <= len.
 * 滑动窗口起点从0开始，起点的终止位置是 len - K。
 * 求所有划过的窗口最大值之和。
 * 如：arr = {3,1,2,5}  K = 3.
 * {3,1,2} ->  3
 * {1,2,5} -> 5
 * 所以sum = 8.
 *
 * @date 2020/3/4 20:57
 */
public class Code04_SlidingWindowMax {
    public static int maxSum1(int[] num, int size) {
        if (num == null || num.length < size) return 0;
        int res = 0;
        //如{1,2,3,4}  len = 4, K= 3, K的最后位置是index = 1 = 4 - 3
        for (int i = 0; i <= num.length - size; i++) {
            int max = num[i];
            for (int j = 0; j < size; j++) {
                max = Math.max(max, num[i + j]);
            }
            res += max;
        }
        return res;
    }

    /**
     * 滑动窗口起始点是L+1，终止点是R。开始L = R = -1.
     *
     * 逻辑： 1、扩大窗口，R++
     * 2、检查起点是否过期. R - L > K ?
     * 3、检查是否形成窗口大小为K，如果是记录窗口内最值。
     */
    public static Integer[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            //1有元素进入窗口，更新最大值
            //当arr[i]大于等于队尾元素 ，一直弹出队尾，直到小于队尾或者队列为空
            while (!queue.isEmpty() && arr[i] >= arr[queue.peekLast()]) {
                queue.pollLast();
            }
            // 这里是最小值机制
//            while (!queue.isEmpty() && arr[i] <= arr[queue.peekLast()]){
//                queue.pollLast();
//            }
            //把arr[i]对应的索引i队尾入队
            queue.offer(i);
            //2左侧缩进窗口，去除失效的最大值
            //queue存的是索引，当前位置是i，窗口长是w，则当前窗口的最左位置是 i-w+1
            if (queue.peekFirst() == (i - w + 1) - 1) {
                queue.pollFirst();
            }
            //如果 i>=w-1代表窗口已经形成，则更新最大值数组res
            if (i >= w - 1) {
                res.add(arr[queue.peekFirst()]);
            }
        }
        return res.toArray(new Integer[0]);
    }

    public static Integer[] getMinWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        List<Integer> res = new LinkedList<>();
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            //1更新队列，使得队列按照从小到大
            while (!queue.isEmpty() && arr[i] <= queue.peekLast()){
                queue.pollLast();
            }
            queue.offerLast(i);
            //2检查是否过期
            if(queue.peekFirst() == i - w) queue.pollFirst();
            //3检查是否已经形成窗口
            if(i >= w -1)
                res.add(arr[queue.peekFirst()]);
        }
        return res.toArray(new Integer[0]);
    }
    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 4, 3, 1, 6, 7};
        int w = 3;
        System.out.println(maxSum1(arr, w));
        System.out.println(Arrays.toString(getMaxWindow(arr, w)));
        System.out.println(Arrays.toString(getMinWindow(arr, w)));
    }

}
